#include "main/utils.h"
using namespace std;

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
      vector<int> dp(time + 1, INT_MAX - 1);
      dp[0] = 0;
      for (int i = 0; i <= time; ++i) {
        for (auto it : clips) {
          if (it[0] < i && it[1] >= i) {
            dp[i] = min(dp[it[0]] + 1, dp[i]);
          }
        }
      }
      return dp[time] == INT_MAX - 1 ? -1 : dp[time];
    }

    int videoStitching1(vector<vector<int>>& clips, int time) {
      vector<int> maxn(time, 0);
      for (auto it : clips) {
        if (it[0] < time) {
          maxn[it[0]] = max(maxn[it[0]], it[1]);
        }
      }
      int pre = 0, last = 0, count = 0;
      for (int i = 0; i < time; ++i) {
        last = max(last, maxn[i]);
        if (i == last) {
          return -1;
        }
        if (i == pre) {
          ++count;
          pre = last;
        }
      }
      return count;
    }
};

int main() {
  vector<vector<int>> clips = {{0, 2}, {4, 6}, {8, 10}, {1, 9}, {1, 5}, {5, 9}};
  int time = 10;
  Solution su;
  cout << su.videoStitching(clips, time) << endl;
  cout << su.videoStitching1(clips, time) << endl;

  return 0;
}
